home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / GRAPHICS / FREETEX.ZIP / FREETEX.TXT
Encoding:
Text File  |  1996-04-26  |  5.6 KB  |  288 lines

  1.  
  2.  
  3.                 
  4.  
  5.                     Free Direction Texture Mapping 
  6.  
  7.                  
  8.  
  9.  
  10. The following article was posted by Hannu Helminen (dm@stekt.oulu.fi) to
  11.  
  12. comp.graphics.algorithms
  13.  
  14.  
  15. The idea of free-direction texture-mapping seems to be new to many
  16.  
  17. few people, so I decided to post this short introduction.
  18.  
  19.  
  20. Warning: The level of this discussion is quite introductory, if you know
  21.  
  22. (or guess) what I'm going to talk about, you probably know as much as I
  23.  
  24. do.
  25.  
  26.  
  27.  
  28. First look at the principles. In Doom (and in Wolfenstain) the method
  29.  
  30. used to draw the walls is quite simple. You divide the wall into
  31.  
  32. vertical lines. Then you calculate where the wall should start and where
  33.  
  34. to end on the screen (A and B in my nice ascii-picture), and where in
  35.  
  36. the texture space the corresponding line should start and end.
  37.  
  38.  
  39. Wall:      Texture:
  40.  
  41.  \            Y
  42.  
  43.   \B       \/\^\/\/\
  44.  
  45.   ^\       /\/./\/\/
  46.  
  47.   . \      \/\.\/\/\
  48.  
  49.   . /      /\/./\/\/
  50.  
  51.   ./          X
  52.  
  53.   /A
  54.  
  55.  /      
  56.  
  57.  
  58. Then you simply do a highly optimized loop in which you do all the
  59.  
  60. pixels in the vertical line, pick a color from the texture, put it onto
  61.  
  62. the screen, and move to next position in the texture.
  63.  
  64.  
  65.  
  66. The floor is a bit more complicated. (I understand that Wolfenstain had
  67.  
  68. no floor texturing, am I correct?) This time, the floor segment is
  69.  
  70. mapped to a horizontal line, which is simple enough. However, in texture
  71.  
  72. space that same line may be in any direction, so you'll have a 2D line
  73.  
  74. in the texture, like this:
  75.  
  76.  
  77. Floor:     Texture:
  78.  
  79.     /\                Y
  80.  
  81.  A/...>\B       \/\/\.\/\
  82.  
  83. /        \      /\/\.\/\/
  84.  
  85.                 \/./\/\/\
  86.  
  87.                 /./\/\/\/
  88.  
  89.                 X
  90.  
  91.  
  92.  
  93.  
  94. This is old and dull. Now for the new and exciting part: suppose we wish
  95.  
  96. to draw a polygon in 3-space that has free orientation. A bit of thought
  97.  
  98. and a simple extension of the above ideas tell us that we should use a
  99.  
  100. free-direction line in the display coordinates as well.
  101.  
  102.  
  103. When we map a plane with free orientation to the screen, there is
  104.  
  105. always one direction on the screen, in which the z-coordinate
  106.  
  107. (distance) stays the same. In doom's walls it is vertical, in doom's
  108.  
  109. floors it is horisontal.  But there is one such direction for every
  110.  
  111. plane.
  112.  
  113.  
  114. Why is constant z-coordinate important? These lines have the special
  115.  
  116. property that constant movement along them corresponds to constant
  117.  
  118. movement in texture space.
  119.  
  120.  
  121. Read the above two paragraphs again until you have understood them,
  122.  
  123. since they are the key thing. The rest is only implementation,
  124.  
  125. following is a short explanation on how I did it.
  126.  
  127.  
  128. For each polygon you are about to draw on the screen, do the following.
  129.  
  130. Find the plane equation. From that, derive the "constant-z" direction.
  131.  
  132. (Come on, take a piece of paper and a pen, it is quite easy.)
  133.  
  134.  
  135. It helps to make the distinction between two cases here.  Either the
  136.  
  137. "constant-z" direction is more horisontal, or it is more vertical.
  138.  
  139. Suppose that it is more horisontal. The constant-z line equation is now
  140.  
  141. something like y = p*x, where -1 <= p <= 1.
  142.  
  143.  
  144.  ----
  145.  
  146.      ---   Example of a constant-z line
  147.  
  148.         ----
  149.  
  150.             ----
  151.  
  152.  
  153. Now, a change in the coordinate system is in order. x is the same x as
  154.  
  155. before, but y is "slanted" by the factor of p. This means that the
  156.  
  157. x-axis will be "slanted" but y-axis will be the same as before.
  158.  
  159.  
  160. The next thing is to convert the polygon to this coordinate system.
  161.  
  162. Scan convert it line by line, but along these "slanted" (constant-z)
  163.  
  164. lines.
  165.  
  166.  
  167. Suppose that we are about to draw a triangle shown below, and the
  168.  
  169. slanted line is the one shown above. So the path to follow on the
  170.  
  171. is as follows (ascii art is back again). The path in the texture is
  172.  
  173. also determined.
  174.  
  175.         
  176.  
  177. On the screen:     In texture (eg.):
  178.  
  179.  
  180.  \-------            Y
  181.  
  182.  A...    -----/      /./\/\/\/
  183.  
  184.    \ ...     /       \/./\/\/\
  185.  
  186.     \   ..../        /\/./\/\/
  187.  
  188.      \     /B        \/\/./\/\
  189.  
  190.       \   /               X
  191.  
  192.        \ /
  193.  
  194.         X
  195.  
  196.  
  197.  
  198. So when you render the triangle, the result would be like this. The
  199.  
  200. numbers are lines of constant Z-value.
  201.  
  202.  
  203.  22221110   
  204.  
  205.   3332221111000
  206.  
  207.    44333222211
  208.  
  209.     544433332  
  210.  
  211.      5554444   
  212.  
  213.       66555    
  214.  
  215.        766     
  216.  
  217.         7      
  218.  
  219.  
  220. Note: you should stack the constant-z lines just as shown in the picture.
  221.  
  222.  
  223. Implementation notes: this will be a bit slower than DOOM floors, since
  224.  
  225. the algorithm is a bit more complicated. Another thing is that it will
  226.  
  227. not be quite as cache-coherent.
  228.  
  229.  
  230. If you are rendering big polygons (and have a large cache), it helps
  231.  
  232. to precalculate the pixels lying on the line, so you need not worry about
  233.  
  234. your Bresenham having to choose right pixels. All you need to do is offset
  235.  
  236. the line to right memory offset.
  237.  
  238.  
  239. The inner loop of this machine could look something like this:
  240.  
  241.  
  242. zbufpointer = zbufbase + offset;
  243.  
  244. pixelpointer = pixelbase + offset;
  245.  
  246.  
  247. while (--count >= 0) {
  248.  
  249.   off = *precalculatedline++;
  250.  
  251.   if (z > zbufpoiner[off]) {
  252.  
  253.     zbufpointer[off] = z;
  254.  
  255.     pixelpointer[off] = texture(x,y);
  256.  
  257.   }
  258.  
  259.   x += dx;
  260.  
  261.   y += dy;
  262.  
  263. }
  264.  
  265.  
  266. There is an error of about 0.5 pixel-lengths, since the pixels lying on
  267.  
  268. the constant-z lines are rounded to nearest pixels.
  269.  
  270.  
  271. Another error can also be seen in the above picture, the line marked
  272.  
  273. with 0's has a small "gap" in it, what should we do with it?
  274.  
  275.  
  276. Happy programming!
  277.  
  278.  
  279. --dm
  280.  
  281. --
  282.  
  283.  
  284.   Hannu    dm@stekt.oulu.fi  || You have been hacking too long when you
  285.  
  286.  Helminen dm@phoenix.oulu.fi || talk of people as users (or end-users)
  287.  
  288.